/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */


#ifndef __BITVECTOR_BITMAP_TEST_HPP__
#define __BITVECTOR_BITMAP_TEST_HPP__

#include <unistd.h>

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/portability/Stream.h>

#include <cubefs/core/bitvector.hpp>
#include "TestBase.hpp"

using namespace std;

namespace cubefs {
namespace core {
namespace tests {
namespace bitvector_ns {


class BitmapTest : public TestBase
{
    CPPUNIT_TEST_SUITE(BitmapTest);

    CPPUNIT_TEST(testSmallEmptyInsert);
    CPPUNIT_TEST(testLargeEmptyInsert);
    CPPUNIT_TEST(testSmallAppend);
    CPPUNIT_TEST(testSmallUDSInsert);
    CPPUNIT_TEST(testLargeUDSInsert);
    CPPUNIT_TEST(testInsertNodeSall);
    CPPUNIT_TEST(testInsertIntoOneHugeNode);

    CPPUNIT_TEST_SUITE_END();

public:
    BitmapTest() {}

    void testSmallEmptyInsert() {
        bv bv0 (mgr);
        bv0.max_node_capacity() = 3;

        buffer<64> buf;
        buf.clear();

        iterator iter(mgr, txn);
        bv0.insert_bitmap_block(iter, buf, 0, 0, 100, bv::BIT_FOR_PARENT);

        node_base *root = get_node(bv0.root());
        check_node(root, 100, 0, 100, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);

        remove_tree(root);
    }

    void testLargeEmptyInsert() {
        bv bv0 (mgr);
        bv0.max_node_capacity() = 3;

        buffer<4096*4> buf;
        buf.clear();

        index_t max = 220;
        csize_t size = createUDS(buf, 1, max + 1, 0, -1);

        index_t rank0 = 0;
        index_t bitsize0 = 0;

        for (index_t c = 1; c <= max; c++) {
            rank0 += c;
            bitsize0 += c+1;
        }

        index_t prefix = 0, offset = 0, rank = 0, bitsize = 0;
        compute_rank_and_size_up_to(buf, prefix, offset, rank, bitsize, size, 4, 0);

        CPPUNIT_ASSERT_EQUAL(rank0, rank);
        CPPUNIT_ASSERT_EQUAL(bitsize0, bitsize);

        iterator iter(mgr, txn);
        bv0.insert_bitmap_block(iter, buf, 0, 0, size, bv::PATH);

        node_base *root = get_node(bv0.root());

        check_node(root, size, rank, bitsize, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);

        remove_tree(root);
    }

    void testSmallAppend() {
        bv bv0 (mgr);
        bv0.max_node_capacity() = 3;

        buffer<4096*4> buf1;
        buf1.clear();

        index_t max = 220;
        csize_t size1 = createUDS(buf1, 1, max + 1, 0, -1);

        index_t prefix1 = 0, offset1 = 0, rank1 = 0, bitsize1 = 0;
        compute_rank_and_size_up_to(buf1, prefix1, offset1, rank1, bitsize1, size1, 4, 0);

        iterator iter(mgr, txn);
        bv0.insert_bitmap_block(iter, buf1, 0, 0, size1, bv::PATH);

        node_base *root = get_node(bv0.root());

        CPPUNIT_ASSERT_EQUAL(size1, bv::get_max_key(root, 0));
        CPPUNIT_ASSERT_EQUAL((csize_t)rank1, bv::get_max_key(root, 1));
        CPPUNIT_ASSERT_EQUAL((csize_t)bitsize1, bv::get_max_key(root, 2));

        buffer<4096> buf2;
        buf2.clear();

        csize_t size2 = createUDS(buf2, 1, 50, 0, -1);

        index_t prefix2 = 0, offset2 = 0, rank2 = 0, bitsize2 = 0;
        compute_rank_and_size_up_to(buf2, prefix2, offset2, rank2, bitsize2, size2, 4, 0);

        iter = get_last(root);

        iter.setEof(true);
        iter.idx() = iter.data()->header().get_size();

        bv0.insert_bitmap_block(iter, buf2, 0, 0, size2, bv::PATH);

        root = get_node(bv0.root());

        check_node(root, size1 + size2, rank1 + rank2, bitsize1 + bitsize2, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);

        remove_tree(root);
    }

    void testSmallUDSInsert() {
        bv bv0(mgr);
        bv0.max_node_capacity() = 3;

        fill_bitvector(bv0, 1, 300);

        node_base* root = get_node(bv0.root());

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        iterator iter = get_first(root);
        skip_nodes(iter, 50, 4, 0);

        buffer<4096*4> buf2;
        buf2.clear();

        csize_t size2 = createUDS(buf2, 1, 10, 0, -1);

        index_t prefix2 = 0, offset2 = 0, rank2 = 0, bitsize2 = 0;
        compute_rank_and_size_up_to(buf2, prefix2, offset2, rank2, bitsize2, size2, 4, 0);

        bv0.insert_bitmap_block(iter, buf2, 0, 0, size2, bv::PATH);

        root = get_node(bv0.root());

        check_node(root, size1 + size2, rank1 + rank2, bitsize1 + bitsize2, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);

        remove_tree(root);
    }

    void testLargeUDSInsert() {
        bv bv0(mgr);
        bv0.max_node_capacity() = 3;

        fill_bitvector(bv0, 1, 300);

        node_base* root = get_node(bv0.root());

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        iterator iter = get_first(root);
        skip_nodes(iter, 50, 4, 0);

        buffer<4096*4> buf2;
        buf2.clear();

        csize_t size2 = createUDS(buf2, 1, 200, 0, -1);

        index_t prefix2 = 0, offset2 = 0, rank2 = 0, bitsize2 = 0;
        compute_rank_and_size_up_to(buf2, prefix2, offset2, rank2, bitsize2, size2, 4, 0);

        bv0.insert_bitmap_block(iter, buf2, 0, 0, size2, bv::PATH);

        root = get_node(bv0.root());

        check_node(root, size1 + size2, rank1 + rank2, bitsize1 + bitsize2, 0);

        iter = get_first(root);
        check_bitmaps(iter, 4, 0);

        remove_tree(root);
    }

    void testInsertNodeSall() {
        bv bv0(mgr);
        bv0.max_node_capacity() = 3;
        fill_bitvector(bv0, 1, 50);

        node_base* root = get_node(bv0.root());

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)-1, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        buffer<8> buf;
        set_bit(buf, 0, 1);

        iterator iter = get_first(root);
        bv0.insert_bitmap_block(iter, buf, 0, 0, 1, bv::BIT_FOR_PARENT);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1, rank1 + 1, bitsize1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)0, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(true, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)0, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(true, iter.data()->header().hasnt_label());

        buf.clear();
        set_bits(buf, 0, 9, 4);

        root = get_node(bv0.root());
        iter = get_first(root);
        iter.move(3);
        bv0.insert_bitmap_block(iter, buf, 4, 0, 4, bv::LABEL);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1 + 4, rank1 + 1, bitsize1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)0, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)0, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(false, iter.data()->header().hasnt_label());

        buf.clear();
        set_bits(buf, 0, 0, 1);

        root = get_node(bv0.root());
        iter = get_first(root);
        iter.move(2 + 1 + 2*4 + 1);
        bv0.insert_bitmap_block(iter, buf, 0, 0, 1, bv::PATH);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1 + 4 + 1, rank1 + 1, bitsize1 + 1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)-1, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)-1, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(false, iter.data()->header().hasnt_label());

        remove_tree(root);
    }

    void testInsertIntoOneHugeNode() {
        bv bv0(mgr);
        bv0.max_node_capacity() = 3;

        fill_bitvector(bv0, 120000, 120001);

        node_base* root = get_node(bv0.root());

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)-1, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        buffer<8> buf;
        set_bit(buf, 0, 1);

        iterator iter = get_first(root);
        bv0.insert_bitmap_block(iter, buf, 0, 0, 1, bv::BIT_FOR_PARENT);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1, rank1 + 1, bitsize1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)0, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(true, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)0, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(true, iter.data()->header().hasnt_label());

        buf.clear();
        set_bits(buf, 0, 9, 4);

        root = get_node(bv0.root());
        iter = get_first(root);
        iter.move(120001 + 1);
        bv0.insert_bitmap_block(iter, buf, 4, 0, 4, bv::LABEL);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1 + 4, rank1 + 1, bitsize1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)0, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)0, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(false, iter.data()->header().hasnt_label());

        buf.clear();
        set_bits(buf, 0, 0, 1);

        root = get_node(bv0.root());
        iter = get_first(root);
        iter.move(120001 + 1 + 120001*4 + 1);
        bv0.insert_bitmap_block(iter, buf, 0, 0, 1, bv::PATH);

        root = get_node(bv0.root());
        check_tree(root, size1 + 1 + 4 + 1, rank1 + 1, bitsize1 + 1 + 1, 4, 0);

        iter = get_first(root);

        BV_NODE_CAST2(root,
            CPPUNIT_ASSERT_EQUAL((short)-1, __root->inserted_idx());
            CPPUNIT_ASSERT_EQUAL(false, __root->hasnt_label());
        )

        CPPUNIT_ASSERT_EQUAL((index_t)-1, iter.data()->header().get_inserted());
        CPPUNIT_ASSERT_EQUAL(false, iter.data()->header().hasnt_label());

        remove_tree(root);
    }
};

} //bitvector_ns
} //tests
} //core
} //cubefs

#endif

